package com.algorithm.algorithm.排序算法;

import java.util.Arrays;
//两边扫描方式快排，称之为一边挖坑一边埋坑，以左边为轴，最右边索引先开始，遇到比轴大时，索引-1，找到比轴小的时候开始确定左索引的位置
//左索引在遇到比轴小的时候索引+1，找到比轴大的时候，开始交换左右索引对应的数据，交换完成之后，右索引继续向左走，重复上述操作，直到左右索引到了一个位置时，一个轴的位置已经确定
//此时交换左轴与左索引对应的数据，一个数的位置已经安排好，剩下的就是将左右两边的数组继续上述操作即可，递归结束条件为左右两边索引到了一个位置即可
public class QuickSort1 {

	public static void main(String[] args) {
		int a[]={3,4,5,1,3,2,6,11,3};
		//int a[]={5,6,11,4};
		quickSort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}

	public static void quickSort(int[] a, int left, int right) {

		if(left<right){
			int i=left;
			int j=right;
			int temp=a[left];
			while(i<j){
				while(a[j]>=temp && i<j){
					j--;
				}
				while (a[i]<=temp && i<j){
					i++;
				}
				if(i<j){
					swap(a,i,j);
				}

			}

			swap(a,i,left);
			quickSort(a,0,j-1);
			quickSort(a,j+1,right);
		}

	}


	public static void  swap(int a[],int left,int right){
		int temp=a[right];
		a[right]=a[left];
		a[left]=temp;
	}

}